package day_7_2;

import java.util.ArrayList;
import java.util.List;

public class Main1 {
    /**
     * 89. 格雷编码
     * https://leetcode.cn/problems/gray-code/description/
     */
    public List<Integer> grayCode(int n) {
        // 公式
        List<Integer> ret = new ArrayList<>();
        ret.add(0);
        int head = 1;
        for(int i = 0;i < n;i++) {
            for(int j = ret.size() - 1;j >= 0;j--) {
                ret.add(head + ret.get(j));
            }
            head <<= 1;
        }
        return ret;
    }
}
